Grokking Tree Coding Patterns for Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Course Overview
Introduction to Tree
Types of Tree
BST Traversal Techniques
BST Operations
Introduction to Level Order Traversal Pattern
Reverse Level Order Traversal (easy)
Solution: Reverse Level Order Traversal
Find Largest Value in Each Tree Row (medium)
Solution: Find Largest Value in Each Tree Row
Maximum Width of Binary Tree (medium)
Solution: Maximum Width of Binary Tree
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Zigzag Traversal (medium)
Solution: Zigzag Traversal
Even Odd Tree (medium)
Solution: Even Odd Tree
N-ary Tree Level Order Traversal (hard)
Solution: N-ary Tree Level Order Traversal
Introduction to Tree Depth Pattern
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Balanced Binary Tree (easy)
Solution: Balanced Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Maximum Depth of N-ary Tree (easy)
Solution: Maximum Depth of N-ary Tree
Find maximum depth of subtree (medium)
Solution: Find maximum depth of subtree
Root to Leaf Path Pattern (medium)
Introduction to Root to Leaf Path Pattern
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Sum of Root To Leaf Binary Numbers (easy)
Solution: Sum of Root To Leaf Binary Numbers
Insufficient Nodes in Root to Leaf Paths (medium)
Solution: Insufficient Nodes in Root to Leaf Paths
Smallest String Starting From Leaf (medium)
Solution: Smallest String Starting From Leaf
Pseudo-Palindromic Paths in a Binary Tree (medium)
Solution: Pseudo-Palindromic Paths in a Binary Tree
All Paths for a Sum (medium)
Solution: All Paths for a Sum
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Path With Given Sequence (medium)
Solution: Path With Given Sequence
Count Paths for a Sum (medium)
Solution: Count Paths for a Sum
Introduction to Leaf Processing Pattern
Sum of Left Leaves (easy)
Solution: Sum of Left Leaves
Leaf-Similar Trees (easy)
Solution: Leaf-Similar Trees
Check if all leaves are at same level (medium)
Solution: Check if all leaves are at same level
Delete Leaves With a Given Value (medium)
Solution: Delete Leaves With a Given Value
Deepest Leaves Sum (medium)
Solution: Deepest Leaves Sum
Introduction to Tree View Pattern
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Top View Of the Binary Tree (medium)
Solution: Top View Of the Binary Tree
Bottom View Of the Binary Tree (medium)
Solution: Bottom View Of the Binary Tree
Boundary of Binary Tree (medium)
Solution: Boundary of Binary Tree
Introduction to Comparison of Two Trees Pattern
Symmetric Tree (easy)
Solution: Symmetric Tree
Mirror Image Trees (medium)
Solution: Mirror Image Trees
Subtree of Another Tree (easy)
Solution: Subtree of Another Tree
Isomorphic Trees (medium)
Solution: Isomorphic Trees
Introduction to Serialize and Deserialize Tree Pattern
Serialize and Deserialize BST (medium)
Solution: Serialize and Deserialize BST
Verify Preorder Serialization of a Binary Tree (medium)
Solution: Verify Preorder Serialization of a Binary Tree
Create Binary Tree From Descriptions (medium)
Solution: Create Binary Tree From Descriptions
Serialize and Deserialize N-ary Tree (hard)
Solution: Serialize and Deserialize N-ary Tree
Solution: Sum of Root To Leaf Binary Numbers

Problem Statement

You are given the root of a binary tree, where each node holds either a 0 or 1. Each path from the root to a leaf forms a binary number.

For example, if the path is 1 -> 0 -> 1, then this could represent 101 in binary, which is 5 in decimal representation. You need to consider all these root-to-leaf paths, convert them to binary numbers and sum them.

Return the total sum of all these binary numbers.

The test cases are generated so that the answer fits in a 32-bits integer.

Examples

Example 1

  • Input: root = [1,0,1,0,1,null,1]
Image
  • Expected Output: 16
  • Explanation: The paths from the root to leaves represent binary numbers 100, 101, and 111. Their decimal equivalents are 4, 5, and 7, respectively. The sum of these numbers is 4 + 5 + 7 = 16.

Example 2

  • Input: root = [1,1,0,1,1,0,1]
Image
  • Expected Output: 23
  • Explanation: The paths represent binary numbers 111, 111, 100 and 101. Their decimal equivalents are 7, 5, 4, and 5, respectively. The sum is 7 + 7 + 4 + 5 = 23.

Example 3

  • Input: root = [1,0,1,null,null,0,1]
Image
  • Expected Output: 15
  • Explanation: The paths represent binary numbers 10, 110, and 111. Their decimal equivalents are 2, 6, and 7, respectively. The sum is 2 + 6 + 7 = 15.

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • Node.val is 0 or 1.

Solution

To solve this problem, we can use Depth-First Search (DFS) to explore all possible paths from the root to the leaves in the binary tree. The idea is to traverse the tree while keeping track of the current binary number formed by the nodes on the path. As we move down the tree, we shift the current number to the left (which is equivalent to multiplying by 2) and add the value of the current node. Once we reach a leaf, we add the complete binary number to our sum.

This approach is effective because it directly mirrors the structure of the problem—each path from the root to a leaf naturally corresponds to a binary number, and DFS allows us to explore these paths efficiently. By accumulating the sum at each leaf, we ensure that all possible numbers are considered, leading to the correct total sum of all binary numbers in the tree.

Step-by-Step Algorithm

  1. Initialize the Process:

    • Start DFS from the root node with currentSum 0.
  2. Check for Null Node:

    • If the current node is null, return 0. This acts as the base case and helps terminate the recursive calls.
  3. Update the Current Sum:

    • Calculate the new currentSum by shifting the previous currentSum left by one bit (equivalent to multiplying by 2) and adding the value of the current node.
    • This can be represented as currentSum = currentSum * 2 + node.val.
    • For example, if you want to append 1 to 10, then you need to leftshif 10, and it will become 100, and now you can add 1 to 100. So, it will become 101.
  4. Check for Leaf Node:

    • If the current node is a leaf (i.e., both left and right children are null), return the currentSum as it represents the complete binary number from the root to this leaf.
  5. Recursive Traversal:

    • Recursively call the dfs method for the left child of the current node and add the result to a sum.
    • Recursively call the dfs method for the right child of the current node and add the result to the sum.
    • Return the sum obtained from both left and right subtree traversals.
  6. Combine Results:

    • In the sumRootToLeaf method, the final returned sum from the dfs method represents the total sum of all root-to-leaf binary numbers.

Algorithm Walkthrough

Let's walk through the algorithm with the example binary tree [1,0,1,0,1,null,1].

Image
  1. Starting at Root Node:

    • The root node is 1. We start the DFS traversal with currentSum = 0.
    • Update currentSum: currentSum = 0 * 2 + 1 = 1.
  2. Move to Left Child (0):

    • Move to the left child of root, which is 0.
    • Update currentSum: currentSum = 1 * 2 + 0 = 2.
  3. Move to Left Child (0):

    • Move to the left child of the previous node, which is 0.
    • Update currentSum: currentSum = 2 * 2 + 0 = 4.
    • Since this node is a leaf, return 4.
  4. Backtrack and Move to Right Child (1):

    • Backtrack to the node with value 0 (parent node).
    • Move to its right child, which is 1.
    • Update currentSum: currentSum = 2 * 2 + 1 = 5.
    • Since this node is a leaf, return 5.
  5. Backtrack to Root and Move to Right Child (1):

    • Backtrack to the root node.
    • Move to its right child, which is 1.
    • Update currentSum: currentSum = 1 * 2 + 1 = 3.
  6. Move to Right Child (1):

    • Move to the right child of the previous node, which is 1.
    • Update currentSum: currentSum = 3 * 2 + 1 = 7.
    • Since this node is a leaf, return 7.
  7. Combine Results:

    • Sum the values from all leaf nodes: 4 + 5 + 7 = 16.
  8. Final Output:

    • The total sum of all root-to-leaf binary numbers is 16.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • The time complexity of the algorithm is , where N is the number of nodes in the binary tree.
  • This is because the algorithm performs a Depth First Search (DFS), which visits each node exactly once.

Space Complexity

  • The space complexity is , where H is the height of the tree.
  • This space is required for the recursive stack used during DFS. In the worst case, if the tree is skewed, the height H could be equal to N, leading to a space complexity of .
  • In the best case, the tree is balanced, and the space complexity would be .
Sum of Root To Leaf Binary Numbers (easy)
Insufficient Nodes in Root to Leaf Paths (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity